package com.cqs.leetcode.string.match;

/**
 * @author lixiaowen
 * @create 2019-12-23
 */
public class RobinKarp {

    //进制
    private final int R = 256;

    //TODO 较大的素数
    private long Q = 18789823788317L;


    /**
     * Hash 一致 可能存在冲突
     * @param str
     * @return
     */
    private long hash(String str) {
        long result = 0;
        for (int i = 0; i < str.length(); ++i) {
            result = (result * this.R + str.charAt(i)) % this.Q;
        }
        return result;
    }


    /**
     * 暴力解法的基础上，借助Q进制改写子串的Hash函数，实现O(1)计算Hash值
     * @param txt
     * @param pattern
     * @return
     */
    public int search(String txt, String pattern) {
        if (txt == null || txt.length() == 0 || pattern == null
                || pattern.length() == 0 || txt.length() < pattern.length())
            return -1;
        long patHash = hash(pattern);
        long hash = hash(txt.substring(0, pattern.length()));
        if (hash == patHash && check(txt, pattern, 0)) return 0;
        long modQM_1 = modQM_1(pattern.length());
        int M = pattern.length();
        //核心代码
        for (int i = M ; i < txt.length(); i++) {
            long hash0 = txt.charAt(i - M) * modQM_1 % Q;
            hash0 = this.R * (hash - hash0 + this.Q) % Q;
            hash = (hash0 + txt.charAt(i)) % Q;
            if (hash == patHash && check(txt, pattern, i-M+1)) return i - M + 1;
        }
        return -1;
    }

    /**
     * 冲突处理
     * @param txt
     * @param pattern
     * @param index
     * @return
     */
    private boolean check(String txt, String pattern, int index) {
        int i = -1;
        while (++i < pattern.length() && index + i < txt.length() && txt.charAt(index + i) == pattern.charAt(i)) ;
        return i == pattern.length();
    }

    /**
     * 计算R^(M-1) mod Q
     * 计算Hash过程中需要使用
     * @param M
     * @return
     */
    private long modQM_1(int M) {
        long result = 1;
        for (int i = 1; i < M; i++) {
            result = result * R % Q;
        }
        return result;
    }

    public static void main(String[] args) {
        String source = "abcded";
        String pattern = "bcde";
        RobinKarp robinKarp = new RobinKarp();
        //System.out.println(robinKarp.check(source, pattern, 1));
        System.out.println(robinKarp.search(source, pattern));
    }
}
